﻿// 1005train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>

using namespace std;

/*
输入
9
5 2 1 5 2 1 5 2 1
输出
6
 */
class Solution01
{
public:
    void backTrack(vector<int>& num_vec, int exec_i)
    {
        if (is_find) return;
        int v_size = num_vec.size();
        if (exec_i==v_size)
        {
            bool is_complete = true;
            for (auto&sum:track_v)
            {
	            if (sum!=split_sum)
	            {
                    is_complete = false;
                    break;
	            }
            }
            if (is_complete)
                is_find = true;
            return;
        }

        int track_size = track_v.size();
        for (int i=0; i<track_size; i++)
        {
            if (i > 0 && track_v[i] == track_v[i - 1]) continue;

            track_v[i] += num_vec[exec_i];

            if (track_v[i]<=split_sum)
            {
                backTrack(num_vec, exec_i+1);
            }
            track_v[i] -= num_vec[exec_i];
        }

	    //backTrack
    }
    Solution01(vector<int>&num_vec)
    {
        //最少的 MVP 得分
	    //v_size到1 找到能被sum整除的数
        int v_size = num_vec.size();
        sort(num_vec.rbegin(), num_vec.rend());
        int sum = accumulate(num_vec.begin(), num_vec.end(), 0);
        int max_num = *max_element(num_vec.begin(), num_vec.end());
    	for (int i=v_size; i>=2; i--)
        {
            if (sum % i != 0) continue;
            split_size = i;
            split_sum = sum / i;

            if (split_sum < max_num) continue;

            track_v = vector<int>(split_size);
            backTrack(num_vec, 0);

            if (is_find) break;

	        //for---
        }

        if (is_find)
        {
            cout << split_sum;
            return;
        }
        cout << sum;

        //Solution01
    }
private:
    bool is_find = false;
    int split_size = 0, split_sum = 0;
    vector<int>track_v;
};


/*
 一支N个士兵的军队正在趁夜色逃亡，途中遇到一条湍急的大河。
敌军在T的时长后到达河面，没到过对岸的士兵都会被消灭。
现在军队只找到了1只小船，这船最多能同时坐上2个士兵。

1）当1个士兵划船过河，用时为 a[i]；0 <= i < N
2）当2个士兵坐船同时划船过河时，用时为max(a[j],a[i])两士兵中用时最长的。
3）当2个士兵坐船1个士兵划船时，用时为 a[i]*10；a[i]为划船士兵用时。
4）如果士兵下河游泳，则会被湍急水流直接带走，算作死亡。
请帮忙给出一种解决方案，保证存活的士兵最多，且过河用时最短。

输入描述：
第一行：N 表示士兵数(0<N<1,000,000)
第二行：T 表示敌军到达时长(0 < T < 100,000,000)
第三行：a[0] a[1] … a[i]… a[N- 1]
a[i]表示每个士兵的过河时长。
(10 < a[i]< 100; 0<= i< N）

输出描述：
第一行：”最多存活士兵数” “最短用时”

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
5
43
12 13 15 20 50
输出
3 40
说明
可以达到或小于43的一种方案：
第一步：a[0] a[1] 过河用时：13
第二步：a[0] 返回用时：12
第三步：a[0] a[2] 过河用时：15

3
43
12 13 15
 */
class Solution02
{
public:
    int getShort(int fast, int slow)
    {
        //一个人划，划的*10
        if (fast * 10 < slow) return fast * 10;
        //两个人划，取决于慢的
        return slow;
    }
    Solution02(int limit,vector<int>&spend_v)
    {
        //spend_v[i]表示i号士兵花费的时间
        //dp[i]表示第i号士兵过河花费最短时间
        sort(spend_v.begin(), spend_v.end());

        int total = spend_v.size();
        vector<int>dynamic_v(total);

        //0号士兵过河时间spend_v[0]
        dynamic_v[0] = spend_v[0];
        //1号跟0号一起过河，花费时间取决于慢的
        dynamic_v[1] = getShort(spend_v[0], spend_v[1]);

        for (int i=2; i<total; i++)
        {
            //从i-1转移，代表i-1和i-2先过去了，剩下i没过
            //0过来，把i接走
            int prev_1 = dynamic_v[i - 1] + 
                spend_v[0] + 
                getShort(spend_v[0], spend_v[i]);

            //从i-2转移，表示现在剩下i-1和i在这边
            //2种方案，0过来，i-1和i一起走，1过来，1跟0一起走
            //0过来，0跟i一起走，0过来，0跟i-1一起走（跟上面的方案合并）
            int prev_2 = dynamic_v[i - 2]
                + spend_v[0]
                + getShort(spend_v[i - 1], spend_v[i])
                + spend_v[1]
                + getShort(spend_v[0], spend_v[1]);

            dynamic_v[i] = min(prev_1, prev_2);

            if (dynamic_v[i]>limit)
            {
	            //说明i过不去，0到i-1之间一共有i人，花费时间dp[i-1]
                cout << i << ' ' << dynamic_v[i - 1];
                return;
            }

        }
        cout << total << ' ' << dynamic_v[total - 1];

	    //Solution02
    }
};


/*
c == 0 代表 a 和 b 在一个团队内
c == 1 代表需要判定 a 和 b 的关系，
如果 a 和 b 是一个团队，输出一行'we are a team',
如果不是，输出一行'we are not a team'
c 为其他值，或当前行 a 或 b 超出 1~n 的范围，输出'da pian zi'

如果第一行 n 和 m 的值超出约定的范围时，输出字符串'Null'

输入
5 7
1 2 0
4 5 0
2 3 0
1 2 1
2 3 1
4 5 1
1 5 1
输出
We are a team
We are a team
We are a team
We are not a team
 */
class Union
{
public:
    unordered_map<int, int>parents;
    
    void addNode(int node_i)
    {
        if (parents.count(node_i)==0)
        {
            parents[node_i] = node_i;
        }
	    //addNode
    }

    int findParent(int node_i)
    {
        if (parents.count(node_i) == 0) return -1;

        while (parents[node_i]!=node_i)
        {
            node_i = parents[node_i];
        }
        return node_i;
	    //findParent
    }

    void unionNode(int node_x, int node_y)
    {
        if (findParent(node_x) != findParent(node_y))
            parents[findParent(node_x)] = findParent(node_y);
	    //unionNode
    }

};

class Solution03
{
public:
    bool checkItem(int total, vector<int>&item)
    {
        //c 为其他值
        //a 或 b 超出 1~n 的范围，输出'da pian zi'
        if (item[2] != 0 && item[2] != 1) return false;

        for (int i=0; i<=1; i++)
        {
            bool is_item = item[i] >= 1 && item[i] <= total;
            if (!is_item) return false;
        }
        return true;
	    //
    }

    Solution03(int total, vector<vector<int>>&origin_v)
    {
        
        int origin_size = origin_v.size();

        for (int i=1; i<=total; i++)
        {
            union_.addNode(i);
        }

        for (int i=0; i<origin_size; i++)
        {
            vector<int>item_v = origin_v[i];

            if (!checkItem(total, item_v))
            {
                cout << "da pian zi";
                if (i != origin_size - 1)
                {
                    cout << '\n';
                }
                continue;
            }

            if (item_v[2] == 0)
            {
                union_.unionNode(item_v[0], item_v[1]);
                continue;
            }

            int root_0 = union_.findParent(item_v[0]);
            int root_1 = union_.findParent(item_v[1]);

            if (root_0!=-1 && root_1 != -1 && root_0==root_1)
            {
                cout << "we are a team";
            }
            else
            {
                cout << "we are not a team";
            }

            if (i!= origin_size -1)
            {
                cout << '\n';
            }
        }


	    //Solution03
    }
private:
    Union union_;
};


string LCS(string str1, string str2) {
    // write code here
    int max_length = 0;
    int pos = -1;

    int row_size = str1.size()+1, col_size = str2.size()+1;
    vector<vector<int>>dynamic_v(row_size, vector<int>(col_size));

    //dp[0][0]=0 dp[0][1]=0

    for (int r = 1; r < row_size; r++)
    {
        for (int c = 1; c < col_size; c++)
        {
            if (str1[r-1] == str2[c-1])
            {
                dynamic_v[r][c] = dynamic_v[r - 1][c - 1] + 1;
                if (dynamic_v[r][c] > max_length)
                {
                    pos = r-1;
                    max_length = dynamic_v[r][c];
                }
            }
        }
    }
    int start_pos = pos - max_length + 1;
    return str1.substr(start_pos, max_length);
}


int main()
{
	{
        //"1AB2345CD","12345EF"
        string str1 = "1AB2345CD", str2 = "12345EF";
        cout << LCS(str1, str2);

        return 0;
	}
	{
        int total, v_size;
        cin >> total >> v_size;


        //n，m(1<=n,m<100000)
        //第一行 n 和 m 的值超出约定的范围时，输出Null
        bool is_total = total >= 1 && total < 100000;
        bool is_size = v_size >= 1 && v_size < 100000;

        if (!is_total || !is_size)
        {
            cout << "Null";
            return 0;
        }

        vector<vector<int>>origin_v(v_size);
        for (int i=0; i<v_size; i++)
        {
            vector<int>item_v(3);
            cin >> item_v[0] >> item_v[1] >> item_v[2];
            origin_v[i] = item_v;
        }

        Solution03 solu(total, origin_v);

        return 0;
	}
	{
        int total, limit;
        cin >> total >> limit;

        vector<int>spend_v(total);
        for (int i=0; i<total; i++)
        {
            cin >> spend_v[i];
        }
        Solution02 solu(limit, spend_v);

        return 0;
	}
    //9
    //5 2 1 5 2 1 5 2 1
    int v_size;
    cin >> v_size;
    vector<int>num_vec(v_size);
    for (int i=0; i<v_size; i++)
    {
        cin >> num_vec[i];
    }
    Solution01 solu(num_vec);


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
